{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# QAOA 求解最大割问题\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 概览\n",
    "\n",
    "在[量子近似优化算法教程](./QAOA_CN.ipynb)中，我们介绍了如何将经典的组合优化问题编码为量子优化问题，并用量子近似优化算法 [1]（quantum approximate optimization algorithm, QAOA）求解。在本教程中，我们将以最大割问题为例来进一步阐述 QAOA。\n",
    "\n",
    "### 最大割问题\n",
    "\n",
    "最大割问题（Max-Cut Problem）是图论中常见的一个组合优化问题，在统计物理学和电路设计中都有重要应用。最大割问题是一个 NP 困难问题，因此目前并不存在一个高效的算法能完美地解决该问题。\n",
    "\n",
    "在图论中，一个图是由一对集合 $G=(V, E)$ 表示，其中集合 $V$ 中的元素为该图的顶点，集合 $E$ 中的每个元素是一对顶点，表示连接这两个顶点的一条边。例如下方图片中的图可以由 $V=\\{0,1,2,3\\}$ 和 $E=\\{(0,1),(1,2),(2,3),(3,0)\\}$ 表示。\n",
    "\n",
    "![G](figures/maxcut-fig-maxcut_g.png \"图 1：一个有四个顶点和四条边的图\")\n",
    "<div style=\"text-align:center\">图 1：一个有四个顶点和四条边的图 </div>\n",
    "\n",
    "\n",
    "一个图上的割（cut）是指将该图的顶点集 $V$ 分割成两个互不相交的集合的一种划分，每个割都对应一个边的集合，这些边的两个顶点被划分在不同的集合中。于是我们可以将这个割的大小定义为这个边的集合的大小，即被割开的边的条数。最大割问题就是要找到一个割使得被割开的边的条数最多。图 2 展示了图 1 中图的一个最大割，该最大割的大小为 $4$，即割开了图中所有的边。\n",
    "\n",
    "![Max cut on G](figures/maxcut-fig-maxcut_cut.png \"图 2：图 1 中图的一个最大割\")\n",
    "<div style=\"text-align:center\">图 2：图 1 中图的一个最大割 </div>\n",
    "\n",
    "\n",
    "假设输入的图 $G=(V, E)$ 有 $n=|V|$ 个顶点和 $m=|E|$ 条边，那么我们可以将最大割问题描述为 $n$ 个比特和 $m$ 个子句的组合优化问题。每个比特对应图 $G$ 中的一个顶点 $v$，其取值 $z_v$ 为 $0$ 或 $1$，分别对应该顶点属于集合 $S_{0}$ 或 $S_{1}$，因此这 $n$ 个比特的每种取值 $z$ 都对应一个割。每个子句则对应图 $G$ 中的一条边 $(u,v)$，一个子句要求其对应的边连接的两个顶点的取值不同，即 $z_u\\neq z_v$，表示该条边被割开。也就是说，当该条边连接这的两个顶点被割划分到不同的集合上时，我们说该子句被满足。因此，对于图 $G$ 中的每条边 $(u,v)$，我们有\n",
    "\n",
    "$$\n",
    "C_{(u,v)}(z) = z_u+z_v-2z_uz_v,\n",
    "\\tag{1}\n",
    "$$\n",
    "\n",
    "其中 $C_{(u,v)}(z) = 1$ 当且仅当该条边被割开。否则，该函数等于 $0$。整个组合优化问题的目标函数是\n",
    "\n",
    "$$\n",
    "C(z) = \\sum_{(u,v)\\in E}C_{(u,v)}(z) = \\sum_{(u,v)\\in E}z_u+z_v-2z_uz_v.\n",
    "\\tag{2}\n",
    "$$\n",
    "\n",
    "因此，解决最大割问题就是要找到一个取值 $z$ 使得公式（2）中的目标函数最大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 编码最大割问题\n",
    "\n",
    "为了将最大割问题转化为一个量子问题，我们要用到 $n$ 个量子比特，每个量子比特对应图 $G$ 中的一个顶点。一个量子比特处于量子态 $|0\\rangle$ 或 $|1\\rangle$，表示其对应的顶点属于集合 $S_{0}$ 或 $S_{1}$。值得注意的是，$|0\\rangle$ 和 $|1\\rangle$ 是 Pauli $Z$ 门的两个本征态，并且它们的本征值分别为 $1$ 和 $-1$，即\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Z|0\\rangle&=|0\\rangle,\\tag{3}\\\\\n",
    "Z|1\\rangle&=-|1\\rangle.\\tag{4}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "因此我们可以使用 Pauli $Z$ 门来构建该最大割问题的哈密顿量 $H_C$。因为通过映射 $f(x):x\\to(x+1)/2$ 可以将 $-1$ 映射到 $0$ 上 并且仍将 $1$ 映射到 $1$ 上，所以我们可以将式（2）中的 $z$ 替换为 $(Z+I)/2$（$I$ 是单位矩阵），得到原问题目标函数对应的哈密顿量\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "H_C &= \\sum_{(u,v)\\in E} \\frac{Z_u+I}{2} + \\frac{Z_v+I}{2} - 2\\cdot\\frac{Z_u+I}{2}\\frac{Z_v+I}{2}\\tag{5}\\\\\n",
    "&= \\sum_{(u,v)\\in E} \\frac{Z_u+Z_v+2I - (Z_uZ_v+Z_u+Z_v+I)}{2}\\tag{6}\\\\\n",
    "&= \\sum_{(u,v)\\in E} \\frac{I - Z_uZ_v}{2}.\\tag{7}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "该哈密顿量关于一个量子态 $|\\psi\\rangle$ 的期望值为\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\langle\\psi|H_C|\\psi\\rangle &= \\langle\\psi|\\sum_{(u,v)\\in E} \\frac{I - Z_uZ_v}{2}|\\psi\\rangle\\tag{8}\\\\\n",
    "&= \\langle\\psi|\\sum_{(u,v)\\in E} \\frac{I}{2}|\\psi\\rangle - \\langle\\psi|\\sum_{(u,v)\\in E} \\frac{Z_uZ_v}{2}|\\psi\\rangle\\tag{9}\\\\\n",
    "&= \\frac{|E|}{2} - \\frac{1}{2}\\langle\\psi|\\sum_{(u,v)\\in E} Z_uZ_v|\\psi\\rangle.\\tag{10}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "如果我们记\n",
    "\n",
    "$$\n",
    "H_D = -\\sum_{(u,v)\\in E} Z_uZ_v,\n",
    "\\tag{11}\n",
    "$$\n",
    "\n",
    "那么找到量子态 $|\\psi\\rangle$ 使得 $\\langle\\psi|H_C|\\psi\\rangle$ 最大等价于找到量子态 $|\\psi\\rangle$ 使得 $\\langle\\psi|H_D|\\psi\\rangle$ 最大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Paddle Quantum 实现\n",
    "\n",
    "接下来，我们用量桨实现 QAOA 来求解最大割问题。有许多方法可以找到参数 $\\vec{\\gamma},\\vec{\\beta}$，我们这里使用经典机器学习中的梯度下降方法。\n",
    "\n",
    "要在量桨上实现 QAOA，首先要做的便是加载需要用到的包。其中 `networkx` 包可以帮助我们方便地处理图。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:04.006915Z",
     "start_time": "2021-04-30T09:11:03.951557Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>pre { white-space: pre !important; }</style>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from IPython.core.display import HTML\n",
    "display(HTML(\"<style>pre { white-space: pre !important; }</style>\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:08.078417Z",
     "start_time": "2021-04-30T09:11:04.569758Z"
    }
   },
   "outputs": [],
   "source": [
    "# 加载量桨、飞桨的相关模块\n",
    "import paddle\n",
    "from paddle_quantum.ansatz import Circuit\n",
    "from paddle_quantum.qinfo import pauli_str_to_matrix\n",
    "from paddle_quantum.loss import ExpecVal\n",
    "from paddle_quantum import Hamiltonian\n",
    "\n",
    "# 加载额外需要用到的包\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "\n",
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "接下来，我们生成该最大割问题中的图 $G$。为了运算方便，这里的顶点从 $0$ 开始计数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:08.411878Z",
     "start_time": "2021-04-30T09:11:08.093215Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAjJUlEQVR4nO3deXSV5bX48e8OgYQwxoIMSk1FQHEoqFWrgAOt/Gpaa53Qqz8rTtU6UHpRm94Otl6N+oNqh1utUKWr1mqv97Y/Nd6iFSesI1JHhAoeFVEEGQLkBBKy7x/7TYgMQnLe8w7n7M9arCUvJ+/Zy5xnn32e8zz7EVXFOedcNEriDsA554qJJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnItQadwBOLerqmrqSoChwHCgO9AN2ARkgUXA4kxtdUt8ETq3c+KnAbukCpLseKAaGAvsB7QAzYAEfzT4U4p9clsAPAXUAY96EnZJ40nXJU5VTV0lMAmYCvQCemAJdlcpsAGoB6YDd2Zqq1eHHadzneFJ1yVGVU1dBXAjcAFW0VaEcNsGrAKeCVydqa1uCOGeznWaJ12XCFU1dWOBe4BKbL42bFlgNTAxU1s9Nw/3d26XeNJ1saqqqSsDbgbOJT/JdmtZYBYwJVNbvTGC53PuEzzputhU1dT1BB4GRhFNwm2VBeYDEzK11esjfF7nPOm6eAQJdy4wAiiPIYRGYCEwxhOvi5JvjnCRC6YUHia+hEvwvCOA2UE8zkXCk66Lw83YlEJcCbdVOTAa+FnMcbgi4tMLLlLBKoXZRDuHuzNZ4Hhf1eCi4EnXRSZYh/tPYHDcsWzHMmCYr+N1+ebTCy5KN2HrcJOoErgh7iBc4fNK10Ui2Nq7jPjncT9NIzDYtwy7fPJK10VlEra1N8lasE0azuWNV7ou74JuYUuBQXHHsguWAUO8O5nLF++n66IwHusW1mlj9unHsSP6c8DgPowc3Jte5V3b/u2M25/h2bdX5Rpjq97AccDfwrqhc+150nVRqMbaM3baOUfsxfH7DwwpnE9VAZyAJ12XJ550XRTG0rF+uNtQ4MO1jby2bC3rNzZz0qg9wolsWyXAuHzd3Dmf03V5FcznbiDHVQvlXUtobLJp1iM+txv3XPTFtn8LeXoBbLNEj0xttQ8OFzpfveDybSiwOdebtCbciLRgcTsXOk+6Lt+GY2eapUkzFrdzofOk6/KtOznO58ZASFZvCFdAPOm6fOtGOpOut3t0eeFJ1+XbJmzxQZoo4Ef5uLzwpOvyLUs6k2427iBcYfKk6/JtEelbD16Kxe1c6NI2GFz6LCaEN/evHjiIg/bsC8Dgvp9c8nv2EXtx3L4DAHhl6RoefPWDXJ+uBIvbudD55giXd1U1dfOAg3O5x7RTD+LUQ4bs9HH3zXuPqfe9kstTAczL1FYfmutNnNsen15wUXiK9MzrtgBPxh2EK1w+veCiUAecD/Ts7A2m3vdKGBXsrmgAHoriiVxx8krXReFRYF3cQeyiemBO3EG4wuVJ1+Vd0BB8GlZFJlkDMM0bmLt88qTronInyX+9lQCz4g7CFbakDwJXIDK11as3LV/yaEvTxkR+oaaqWWCGH0rp8s2Trss7ERkgIvd++Psrq1sa1yeyD0NLw9ouH9w5eVbccbjC50nX5Y2Ys4E3gNO1eeOGtc/86ZagqkyMlqaNuuK/r+u2afniZ0TkhyLSLe6YXOHypOvyQkQ+iy0V+z2wG/AIcMC6eQ9OEZFZJKe3QRb0txvfX3A71hHtp8ALIuKbI1xeeNJ1oRKREhG5BHgd+AqwBpgETFDVTPCwKcB8oDGOGNtpBOaXdC2/TFW/hZ0CvBg4CHhORG4SEe+r60Ll24BdaERkODATO4gS4L+BS1X1w60fW1VT1xOYC4wgx/PTOqkRWAiMydRWr2+9KCIVWLU7BStK3gIuUNUnYojRFSCvdF3ORKRURK4CXsYS7nLgVFU9ZXsJFyBIdGOwijfqqYYs8BJbJVwAVW1Q1anAF4HXgH2Ax0XkVhHpHXGcrgB50nU5EZHPA88BN2IV6++Akar6Xzv72SDhHYut4Y0q8WaD5ztu64Tbnqo+DxwCXAM0ARcDr4tIdRRBusLl0wuuU0SkHPgBcDXWw+Nd4CJVnd2Z+1XV1I0B7gUqyc/5ZFlgNTAxU1s9tyM/KCIHAL8FDgsu/QH4jqquDDdEVwy80nUdJiJHYtMC/wZ0AX4JHNDZhAsQJMJh2JxwI+FtGW4I7jcTGNbRhAugqq8BRwLfxZL3WcACETlDRBK57tgll1e6bpeJSE/gOuBy7PDGhcD5qvp0mM9TVVNXCZwLTAV6AxV0rEBowZJtPdbzYVZYO81EZCgwA5sWAbgf+Laqvh/G/V3h86TrdomIfBm4HagCNmNzuNeqat6WfVXV1JUA47GlZ+OAkVhCbW5p3NAHEUrKKuqxXr2lWGJ+A+uH+xAwJx/Na4Lq9nxgOvamUI+9QcxUH1BuJzzpuk8lIpVYcpkUXJoPnKeq/4g6liAJ7w0MX/Hn6+vo0pX+J155KvaRfxGwOFNbHdkLWkT2AG4FvhZcegy4UFX9qB+3Q5503Q6JyMnAfwADsSPJrwGmq2pTnHEBiIgCqGqsc6pB1Xs6Nq/dH3sD+AHwc1XdHGdsLpk86bptiMhA4FfAKcGludgGgYXxRfVJSUm6rUSkH3AL9iUbwPPYfPdrsQXlEslXL7g2QYOab2LzoqcA64HLgKOTlHCTSFVXqurZwFeBpdjyspdE5MfeQMe155WuA0BE9gJ+A0wILv0VuFhV34kvqh1LWqXbXrBz7QbgkuDSa1jV+3x8Ubmk8Eq3yAUNai7DGtRMAFYB5wAnJDXhJp2q1qvqt4FjsN4NBwDPiMj0oLeDK2Je6RYxEdkX2zRwVHDpP4HLVXV5fFHtmiRXuu0FXcquwZaUlQBLsPnxx+KMy8XHK90iJCJdReT7WIOao4APgZNV9fQ0JNw0UdWsql4NHA68gi15myMit4tIn3ijc3HwSrfIiMho4A5gVHDpDmCqqqbqbLC0VLrtiUhXrFfFD7GG6cuwefMHYg3MRcqTbpEIGtT8GLgS65eQwRby/y3OuDorjUm3lYiMxBroHBFcuge4QlVXxBeVi4pPLxQBERmDTSV8D/ud3wIcmNaEm3aq+gbWS/g7WI+IM7AGOmd5A53C55VuARORXkAtcGlwaQG2dOmZ+KIKR5or3fZE5HNYT4svBZfqgEtU9b34onL55JVugRKRCdj60EuBZuBaYHQhJNxCoqpvA8djDXTWAtVYs/SLRcTHZwHySrfAiMhngJ9ha20B5mHV7cvxRRW+Qql02xORwVivi5OCS09g8+7/jC0oFzp/Jy0QwRbeU7EtvOdgjbuvAo4otIRbqFR1GXAycBrwEXA08IqIXCkipbEG50LjlW4BEJFBWIX0jeDSk1iFtCi+qPKrECvd9orlE0sx8ko3xYLqdhJW3X4DWIft9z+2kBNuMVDVj1X1m1gD93exQzJfFJFrRaQs3uhcLrzSTantfOv9ELbQvii+9S70Sre9Ql6FUoy80k0ZEekiIldgKxO+BHwMnA18tVgSbrFR1XWqehl2ZNEiYD/gaRG5RUR6xBud6yivdFMk2Mk0E/hicOkeYLKqfhRfVPEopkq3vWBn4Y+wL0lTv7OwGHnSTYEd7Nm/RFXvjzWwGBVr0m0lIgdjW4lHBZfuAP5VVdfEFZPbNZ50E05EDsEG1EHBpRnAVcU+uIo96ULbm/FUrKdGGfABdhz8X+KMy306T7oJtYM+rBeq6pw440oKT7pbBH2RfwscGVxKTV/kYuRfpCWQiIzDGtRcFVz6GdagxhOu24aqvgmMBS4HNmCbKxaIyDneQCd5vNJNkO2crfU6tjToufiiSiavdLdvB2fdfUtV340vKtde0Sbdqpq6EmAoMBzojn1BtQnIYstyFmdqq1uiikdETsAGy55AE3A9cL2qbooqhjTxpLtjQXV7DnAzUImd6vw94FZVjew1nbQxlhRFk3SDF8B4rIvTWGytYwvWgUuCPxr8KcWmXhYAT2Ht9h7NxwtERPph/W3PCi69gFW3r4b9XIXEk+7OichA4JfAqcGludj5bAvz8XxJHWNJU/BJt6qmrhKYhH0h1Qvogf3yd5Vi82T1wHTgzkxtdc5H2wTVyOnYoOiPvfv/ELhFVTfnev9C50l314nIycCvgQHARuwL2umq2hTG/ZM6xpKqYJNuVU1dBXAjcAH2bhvG0dcN2LvzTODqTG11Q2duErTwuxU4Mbj0OLYy4a0QYiwKnnQ7RkQqsYQ2Kbg0H/tENb+z90zyGEuygky6VTV1Y7HdWpXYXFLYssBqYGKmtnrurv5QUN2eD0wD+mDv7FOBmVqIv4g88qTbOSJyPNazYy9gM5Y0r1XVxo7cJ6ljLA0KKulW1dSVYV8enEt+XghbywKzgCmZ2uqNn/ZAEdkb29hwXHDpAWxX2ft5jbBAedLtPBHpCVyHLTETYCFW9T69s59N8hhLi4JJulU1dT2Bh7FtkVG8GFplsY9qEzK11eu3/kcR6QJcgb3IuwMrsRf7vV7ddp4n3dyJyJHYpop9sXnVXwHfV9VtXseQ3DGWNgWRdIMXw1xgBFAeQwiNWLUwpv2LQkQOwF7UhwWX7sYa1KyMPsTC4kk3HEEDnR9gvT1KgXewdb2z2z8uqWMsjVKfdIOPO48Bo4nnxdCqEXgJOO6dG76qQA3wb0BX4H2s1+2DMcZXUDzphktERmEFwsHBpd8B31XVVUkcY2meaiiEbcA3Yx934nwxEDz/6KY1H/4eO1rlGizh3gbs7wnXJZmq/gM4HNtEsRH4JvCGiJxCwsYYti0+tVKddINvUM8l2vmlT9O9S4/K08r2HHkA8BZwjKpeoqpr4w7MuZ1R1WZVvRHraPcUMKBsz/3v0+ami0jQGAMmVdXUjYk7kM5K7fRCsEbwn8DguGPZWkvjhvX18+6vWvPkXR/HHUuh8umF/BKRkpKKvpcNOu8Xt5T23C2J/4+XAcPSuI43zZXuTdgawcQpKe/Rpe9RZ/447jic6yxVbRlyxV3Du/SoTOrcaSXWHCp1UlnpBtsOlxH/HNOnaQQGF/J2xjh5pZtfPsbyJ62V7iRs22GStWDzzc6lkY+xPEldpRt0MloKDOrsPXqXl/LlkQM4rOoz7D+4N/17lVFZ0Y2NzZvJfNzAnDc/4o6n32ZtNud+IMuAIcXQOSlqXunmTxhjDKBvRVcuHLM34/fbnSGV1pbhvdUNPLrgI25/akkY4wtSOMZK4w6gE8ZjnYw67ah9+jH9tFHbXO9WWsKBe/ThwD36cMYXhvAvM59l8YoNuTxVb2zbr5/U6tIk5zE2fEBPfn/e4Qzo/cnZiX0H9mbfgb059ZA9+b93PMei5Tnvc0jdGEvj9EI11jouZ/XZJh54eRnTH1nI7U8uYXn9lp4fA3qXc/1JB+b6FBXACbnexLmI5TTGykpLuO3sQ9oS7tpsE7c9sZjbnljcVt0O6F3OrWcdQllpzikodWMsjZXuWDrWq3Mbaxqa+MkDr/PHF96lsWnLp5LbnlzM7Mnj6N+rDIAvVO1Gj25d2LCp0+1tS4BxucTqXAxyGmMnjdqDvfv1bPv75Hvm8/iiFQA8+/bHzDrXdsUP7d+Tr4/agz+9+F4usaZujKWq0g3mmkbmep9nlnzMnX/PfCLhAqzasIkXMqva/l5SInTN/Z14ZFVNnc87ulQIY4xN2H9g23/XNza1JVyAJxatYF3jlrnc/9PusTlI1RhLVdLFzlvK66kKQ/tveYfOfLyBNQ05T/a3YHE7lwY5j7GRg3q3/ffSVZ/cu6AKS1dn2/6+36Ccpo5bpWqMpS3pDsfOW8qLyeOHMWLglhfBzx5ZFMZtm7G4nUuDnMdYZUXXtv9et3HbW61r3HJtt4puuTxVq1SNsbTN6XYnx/nc7RGBfzthPy4Ys3fbtVv+toj7X14Wyu1Jzr5153Ym1DEm27mVhD8RkKoxlrak242Qk26Pbl34xZmjGb/vAABaWpTav77JjKeWhPUUApSFdTPn8iznMba6oYmBfboA0Kt82xTTs2zLtVUNm3J5qlapGmNpS7qbsA73odijb3dmnnMo+wVzUA2bmpnyp5eZ/fqHYT0FWLxJ3b/u3NZyHmNvfFDPwD62XGzPyu6I2FwuWJU7ZLct51cu+GBdLk/VKlVjLG1zullCSrqjh/TlL98+si3hLluT5bTbngk74YLFm93po5xLhpzH2MNvbBlDvcq7cszw3dv+fszw3T9R6YY03lI1xtJW6S4ihJgP/mwld19wOOVd7SNQ8+YWHnzlA47cpx9H7tPvE4998JVlfLC2Qwelbq0Ui9u5NMh5jP15/vtcNG7vtrW6P584iruffxeAMw/7bNvjlqxcz1/+Ecq5rKkaY2lLuosJoTrfu1+PtoQLUNqlhIvG7b3dx766dE2uSbcEi9u5NMh5jG1sbuHiu+Zx13mHs3vvcnp378rFR39yRddH9Y1cfNc8NjaH0jIhVWMsVdMLQVOLBXHH0UFvZGqr09VVyBWtsMbYouXrOf7nT/Lrx99i0fJ1NGxqpmFTM4uWr+PXj7/F8T9/Moy+C61SNcbSVumCHSMymhy+Yb3vpaXc99LS8CLasRbgySieyLkQ5TzGwLbb3zR7ITfNXhhOVNuXujGWqko3UAfk1PorQg3AQ3EH4VwH+RjLozQm3UeBUNaZRKAemBN3EM51kI+xPEpd0g3mnKZh73BJ1gBMS1NzZefAx1i+pS7pBu4k+bGXALPiDsK5TvIxlidJ/5+6XcFBdDNJ6IJo3dy8SVVnpO3APOdaZWqrVzetfO+vLU0bk7oqIAukcoylMukGrgYS+T98c8Oabu/dfPr+IvK5uGNxrqNEpK+IzPhg1ndOamlcn9Q+tauA78UdRGekNulmaqsbgIkkrNrVls2bVt4/ba1uyh4HvCYik0Wky05/0LkEEJGvA28AF2jzxk1rn/rDDFVN1BjDxvzEIAekTmqTLkCmtnouNqeTlBdFVkq6zNz43mvDgHuw85tuAeaKSM4nXjiXLyKyu4jcA/wFOwX4GWDUupdnXyQis0jQGAPuzNRWPx13IJ2V6qQbmALMB3LaqxuCxiCO76rqClU9E/g6dkT0EcB8EfmhiITStdm5MIg5G9uFNhFbETAZGKuqrTvTEjfGYo4jJ6Ka1HnyXVdVU9cTmAuMAMp38vB8aAQWAmMytdWf2NsoIn2A/wdcGFx6BThfVV+MNsTCIiIKoKpJnXNMPBEZAtzGltN0HwG+papvb/3YJI+xtCmESpfglzAGexeM+mNQFniJHbwYVHWtql4EjAeWAAcBz4nITSKSmm73rnCISImIXAK8jiXcNcAkYML2Ei4ke4ylTUEkXWh7URyLrS+M6kWRDZ7vuJ29GFR1DnAgMD24dCXwiogcnd8QndtCRIYDjwG/BnoBfwZGquos3cnH3qSPsbQoiOmFrVXV1I0B7gUqyc/ZSVlsudrE4Mu8DhGRw4DfAgcEl24DrlbV+vBCLGw+vdAxIlKKzYX+BJseWA5cqqr/1Zn7JX2MJVnBVLrtBb+kYdgGikbC287YENxvJjCssy8GVX0eOAS4BmgCLgZeF5HqkOJ0ro2IfB54DrgRS7i/w6rbTiVcSP4YS7KCrHTbq6qpqwTOBaYCvbFlXB15s2nBXgj12H70WWHughGRA7Cq97Dg0h+A76jqyrCeoxB5pbtzIlIG/ADbRFAKvAtcpKqzw3yepI+xpCn4pNuqqqauBPsy6yvAOGAk9stuxvqGCnbWkmIv0BJskfiTWOu4OflqrBFsnpgM/Dv2UW0lcDlw787m2YqVJ91PJyJfxN7M98Ne0/8BfF9V89Y9LMljLEmKJuluLXiB7A0MxxJdGXaiaBY7b2lx1N3oRWQoMAP7sgLgfuDbqhrKQVKFxJPu9olIT+zN+wosyS0ELlDVyD+mJ3GMJUHRJt2kEhEBzsdWOfTGPnJNBWZ61buFJ91ticiXgduBKmAzcBPwU1WNe1ODa8eTbkKJyB7ArcDXgkuPAReqamoO4MsnT7pbiEgl9iY9Kbj0D+A8VZ0fW1Buhwpy9UIhCKYUvg6cAazAphxeFZHvegMd10pEvoHNi07CPrp/HzjME25yeaWbAiLSD2ucc1Zw6XlsK/FrsQUVs2KvdEVkIPBL4NTg0tPY3O2b8UXldoVXuimgqitV9Wzgq8BSbHnZSyLyY2+gU1yCBjXnYNXtqcB64DJgnCfcdPBKN2VEpDe2yP3i4NJrWNX7fHxRRa8YK10R2Qv4DTAhuDQba1DzTnxRuY7ySjdlVLVeVS8BjgHewrYSPyMi00SkItbgXF4EDWouwxrUTMC2x34T+Ion3PTxSjfFgi5l12BLykqwLmYXqOpjccYVhWKpdEVkBLbJ4ajg0n3AZaq6PL6oXC680k0xVc2q6tXA4cCr2EL0OSLym6CPr0spEekqIjXAy1jC/RA4WVVP84Sbbl7pFojgC7WrgB8C3bATKy5W1QdiDSxPCrnSFZHRWHU7Orh0BzBVVQu2H0Ex8aRbYIKz2H6LHREEdlbbFaq6Ir6owleISVdEyoEfYW+eXYAMtiHmb3HG5cLl0wsFRlXfwDr8fwfr3HQGsEBE/iXYYuwSSETGYDvJarBx+XPgQE+4hccr3QImIp/D9uJ/KbhUB1yiqu/FF1U4CqXSFZFeQC1waXBpAbYE8Jn4onL55JVuAQvOuzoea6CzFqjGmqV/S0T8dx8zEZmArbO+FGt/+O/AaE+4hc0r3SIhIoOxnqonBZeewOYL/xlbUDlIc6UrIrsBNwPnBJfmYdXty/FF5aLi1U6RUNVlwMnA6cBHwNHYwZhXBudnuQiIyKnYFMI52LE0VwFHeMItHl7pFiER+QzwM7ZUWi9ildYr8UXVMWmrdEVkEPAr7I0P7LSEC1V1UXxRuTh4pVuEVPVjVf0mdqzKu8ChwDwR+WlwrpYLSdCgZhLWoOZkYB1wCXCsJ9zi5JVukdvOt+dvYFXvs/FFtXNpqHS3s3rkf7AGNalfPeI6zyvdIqeq61T1MuwgwUXYYYJ/F5GbRaRHvNGlk4h0EZErsJUJXwI+Bs4Gqj3hOq90XZtgR9SPgSuxHVFvY0d2J26BflIrXRHZD9sR+MXg0j3AZFX9KL6oXJJ40nXbEJGDscQxKrh0B/Cvqromrpi2lrSkKyJdsZUIP2JL74tLVPX+WANzieNJ121XkESuxCrfbsAH2HHwf4kzrlZJSroicgj2xnRQcGkGcFWS3qRccnjSdZ9KRPbFqt4jg0v/CVwed3vBJCTdHfQzvlBV58QVk0s+T7pup4Itw98GbgB6AKuwhjp3aYQvoKqauhJgKDB8xZ9rH6RLKf1PvPI0IIt9Cbg4U1vdEkUsIjIOmAkMA1qwg0N/pKobonh+l16edN0uE5Eq7Iyu44NL/4P17H03H88XJNnxWM+IscB+WIJrbtm4oQ8IJWUV9YACpVi1uQB4Cmvu82jYSTg4o+4GbK0t2BE656vqc2E+jytcnnRdhwTtIc/BegdUYqfRXg3cpqqhJLiqmrpKYBL2sb0XVl13ZBpBgQ1APTAduDNTW51zA3AROQG4DRgCNAHXA9er6qZc7+2Khydd1ykiMhDb1npKcGkudj7bws7es6qmrgI76fgCrKIN46DNBqwCnglcnamtbujoDUSkH/Ymc3Zw6QWsun01hPhckfGk63IiIqdg3csGABuxL5amqWpzR+5TVVM3FlvTWgl0DzlMsHnf1cDETG313F35gaCqPx34JdA/uMcPgVtUdXMeYnRFwJOuy1nQqnA6cG5w6SWsEvzHzn62qqauDKsizyU/yXZrWWAWMCVTW71xRw8KWmHeCpwYXHocW5nwVr4DdIXNk64LjYgcj/Ua2AvYjE0VXKuqjdt7fFVNXU/gYWwTRhQJt1UWmA9MyNRWr2//D0F1ez4wDeiDzQtfCcwMa87aFTdPui5UItITuA64HPvy602s6v17+8cFCXcuMAIojzpOrJftQmBMa+IVkb2xjQ3HBY95ENtVtjSG+FyB8oY3LlSqul5VJ2NLvN4E9gXmisgvgoTcOqXwMPElXILnHQHM3v20a7qLyBSsQc1xwErgTOBET7gubJ50XV6o6tPAaKzqbcEq39eCKYibsSmFuBJuq3LVloNbGte/jTV17w7cDeynqvdEufHDFQ9Pui5vVLVRVX+ANUmfD+xVtuf+s3Vz00VEO4e7QyIl5RUjjhxQ9tmDVgBfU9WzVHVl3HG5wuVzui4SIlJa0r339wad96trS3vtFnc421Bt+VCkZGhn1vE61xFe6bpIqGrzkMl3D+zSo+92VzLETaSkD7a917m88krXRSLY2ruM+OdxP00jMDiMLcPO7YhXui4qk7Av1JKshS0bPJzLC690Xd4F3cKWAoM6e48pXxrG/oP7sM/uPams6EaPbl3INm3m/TVZXsys5vfPvsPC5evCCHcZMCSqFpGu+JTGHYArCuOxbmGdNnn88G2u9epSwr4Du7LvwN6cfugQLr37JR5ZkHNv9d7YWt3EnQvnCoMnXReFaqw9Y6etWLeRF99ZxburGljb0ERFWSljh/Xj83v2BaBbaQlXTRgRRtKtAE7Ak67LE0+6Lgpj6Vg/3G184fptc+D0RxbytylHM7R/TwCG7BZGJ0hKsOPoncsL/yLN5VUwnzsyzHuKQN+KrnztoMHs0XfLHos3PwxlThdgZFVNXewHXrrC5JWuy7ehWMexnO3Ztztzrz5uu/+2asMmfvLA62E8DdgqhqGAt3F0ofNK1+XbcKBDDc076p/L13HmjGeZ/96asG7ZjMXtXOg86bp8606O87mt1mSbuO6hBdz41ze54+m3yXxsB+8OG9CL/3/pUZz4+cFhPA1YvInoDeEKj08vuHzrRkhJd/3GZmY8taTt79c9tIDfTTqMMfv0o7xrF244+UCeWfwxK9bv8ECIXSVAWa43cW57vNJ1+bYJO503dJtblEfbLRGr6FbKqCF9w7i1Yue9ORc6T7ou37LkmHQPq9qNPt27bnNdBI4Z0f8T1zSc/K5Y3M6FzqcXXL4tIsfX2emH7snXPj+Y55as4vVla6lvbKayohvHjujPsAFbNrrVNzbx3JJVucYLFu+iMG7k3NY86bp8W0wIn6jKSrswbnh/xg3vv91/X9fYxBV/nM+6jaEslCjB4nYudN7wxuVdVU3dPODgzv78F6oqOeHAQYweUsmgPuX0rbCphvpsE0tWbGDu4pX88fl3Wbl+U1ghz8vUVh8a1s2ca88rXReFp7Dz0jq1iuGFzGpeyETW4rYFeDKqJ3PFx79Ic1GoAzbEHcQuagAeijsIV7g86booPAqE1hghz+qBOXEH4QqXJ12Xd0FD8GlYFZlkDcA0b2Du8smTrovKnST/9VYCzIo7CFfYkj4IXIEIDnucSXI3HWSBGX4opcs3T7ouSlcDSU1qq4DvxR2EK3yedF1kMrXVDcBEklftZoGJQXzO5ZUnXRepTG31XGzeNCmJNwvcmamtfjruQFxx8KTr4jAFmA80xhxHYxDHd2OOwxUR3wbsYlFVU9cTmAuMAMpjCKERWAiMydRWr4/h+V2R8krXxSJIdGOwSjPqqYYs8BKecF0MPOm62AQJ71hsDW9UiTcbPN9xnnBdHHx6wSVCVU3dGOBeoJL8nE+WxZarTQy+zHMuFl7pukQIEuEwbANFI+FtGW4I7jcTGOYJ18XNK12XOFU1dZXAucBUoDdQQccKhBYs2dZjPR9m+U4zlxSedF1iVdXUlQDjga8A44CRWEJtxnrzCnaemWK9oUuAN7B+uA8Bc7x5jUsaT7ouNYIkvDcwHJv3LcNO7c1iZ5otztRW+wvaJZonXeeci5B/keaccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxH6X4ZvoaaQCRNmAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# n 是图 G 的顶点数，同时也是量子比特的个数\n",
    "n = 4\n",
    "G = nx.Graph()\n",
    "V = range(n)\n",
    "G.add_nodes_from(V)\n",
    "E = [(0, 1), (1, 2), (2, 3), (3, 0), (1, 3)]\n",
    "G.add_edges_from(E)\n",
    "\n",
    "# 将生成的图 G 打印出来\n",
    "pos = nx.circular_layout(G)\n",
    "options = {\n",
    "    \"with_labels\": True,\n",
    "    \"font_size\": 20,\n",
    "    \"font_weight\": \"bold\",\n",
    "    \"font_color\": \"white\",\n",
    "    \"node_size\": 2000,\n",
    "    \"width\": 2\n",
    "}\n",
    "nx.draw_networkx(G, pos, **options)\n",
    "ax = plt.gca()\n",
    "ax.margins(0.20)\n",
    "plt.axis(\"off\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 编码哈密顿量\n",
    "\n",
    "量桨中，哈密顿量可以以 `list` 的形式输入。这里我们构建式（11）中的哈密顿量 $H_D$。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:08.426170Z",
     "start_time": "2021-04-30T09:11:08.418352Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-1.0, 'z0,z1'], [-1.0, 'z1,z2'], [-1.0, 'z2,z3'], [-1.0, 'z3,z0'], [-1.0, 'z1,z3']]\n"
     ]
    }
   ],
   "source": [
    "# 以 list 的形式构建哈密顿量 H_D\n",
    "H_D_list = []\n",
    "for (u, v) in E:\n",
    "    H_D_list.append([-1.0, 'z'+str(u) + ',z' + str(v)])\n",
    "print(H_D_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到，在这个例子中，哈密顿量 $H_D$ 为\n",
    "\n",
    "$$\n",
    "H_D = -Z_0Z_1 - Z_1Z_2 - Z_2Z_3 - Z_3Z_0 - Z_1Z_3.\n",
    "\\tag{12}\n",
    "$$\n",
    "\n",
    "我们可以查看哈密顿量 $H_D$ 的矩阵形式，并且获取它的本征值信息："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:08.792299Z",
     "start_time": "2021-04-30T09:11:08.777145Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-5.  1. -1.  1.  1.  3.  1. -1. -1.  1.  3.  1.  1. -1.  1. -5.]\n",
      "H_max: 3.0\n"
     ]
    }
   ],
   "source": [
    "# 将哈密顿量 H_D 从 list 形式转为矩阵形式\n",
    "H_D_matrix = pauli_str_to_matrix(H_D_list, n)\n",
    "# 取出 H_D 对角线上的元素\n",
    "H_D_diag = np.diag(H_D_matrix).real\n",
    "# 获取 H_D 的最大本征值\n",
    "H_max = np.max(H_D_diag)\n",
    "\n",
    "print(H_D_diag)\n",
    "print('H_max:', H_max)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 搭建 QAOA 电路\n",
    "\n",
    "前面我们介绍了 QAOA 需要将两个酉变换 $U_C(\\gamma)$ 和 $U_B(\\beta)$ 交替地作用在初始态 $|s\\rangle = |+\\rangle^{\\otimes n}$ 上。在这里，我们使用量桨中提供的量子门和量子电路模板搭建出一个量子电路来实现这一步骤。要注意的是，在最大割问题中，我们将最大化哈密顿量 $H_C$ 的期望值的问题简化为了最大化哈密顿量 $H_D$ 的期望值的问题，因此要用到的酉变换也就变成了 $U_D(\\gamma)$ 和 $U_B(\\beta)$。通过交替地摆放两个参数可调的电路模块，我们得以搭建QAOA电路\n",
    "\n",
    "$$\n",
    "U_B(\\beta_p)U_D(\\gamma_p)\\cdots U_B(\\beta_1)U_D(\\gamma_1),\n",
    "\\tag{13}\n",
    "$$\n",
    "\n",
    "其中，$U_D(\\gamma) = e^{-i\\gamma H_D}$ 可以由下图中的电路搭建实现。另一个酉变换 $U_B(\\beta)$ 则等价于在每个量子比特上作用一个 $R_x$ 门。\n",
    "\n",
    "![U_D circuit](figures/maxcut-fig-cir_ud.png \"图 3：酉变换 $e^{i\\gamma Z\\otimes Z}$ 的量子电路实现\")\n",
    "<div style=\"text-align:center\">图 3：酉变换 $e^{i\\gamma Z\\otimes Z}$ 的量子电路实现 </div>\n",
    "\n",
    "\n",
    "因此，实现一层酉变换 $U_B(\\beta)U_D(\\gamma)$ 的量子电路如图 4 所示。\n",
    "\n",
    "![U_BU_D circuit](figures/maxcut-fig-cir_ubud.png \"图 4：酉变换 $U_B(\\beta)U_D(\\gamma)$ 的量子电路实现\")\n",
    "<div style=\"text-align:center\">图 4：酉变换 $U_B(\\beta)U_D(\\gamma)$ 的量子电路实现 </div>\n",
    "\n",
    "量桨中，电路运行前每个量子比特默认的初始状态为 $|0\\rangle$（可以通过输入参数来自定义初始状态），我们可以通过添加一层 Hadamard 门使每个量子比特的状态由 $|0\\rangle$ 变为 $|+\\rangle$，由此得到 QAOA 要求的初始态 $|s\\rangle = |+\\rangle^{\\otimes n}$。在量桨中，可以通过调用 `superposition_layer()` 在量子电路中添加一层 Hadamard 门。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def circuit_QAOA(p):\n",
    "    # 初始化 n 个量子比特的量子电路\n",
    "    cir = Circuit(n)\n",
    "    # 制备量子态 |s>\n",
    "    cir.superposition_layer()\n",
    "    # 搭建p层U_D电路\n",
    "    cir.qaoa_layer(E,V,p)\n",
    "    \n",
    "    return cir\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "搭建 QAOA 量子电路的工作完成后，如果运行该量子电路，得到的输出态为\n",
    "\n",
    "$$\n",
    "|\\vec{\\gamma},\\vec{\\beta}\\rangle = U_B(\\beta_p)U_D(\\gamma_p)\\cdots U_B(\\beta_1)U_D(\\gamma_1)|s\\rangle.\n",
    "\\tag{14}\n",
    "$$\n",
    "\n",
    "### 计算损失函数\n",
    "\n",
    "由上一步搭建的电路的输出态，我们可以计算最大割问题的目标函数\n",
    "\n",
    "$$\n",
    "F_p(\\vec{\\gamma},\\vec{\\beta}) = \\langle\\vec{\\gamma},\\vec{\\beta}|H_D|\\vec{\\gamma},\\vec{\\beta}\\rangle.\n",
    "\\tag{15}\n",
    "$$\n",
    "\n",
    "要最大化该目标函数等价于最小化 $-F_p$。因此我们定义 $L(\\vec{\\gamma},\\vec{\\beta}) = -F_p(\\vec{\\gamma},\\vec{\\beta})$ 为损失函数，即要最小化的函数，然后利用经典的优化算法寻找最优参数 $\\vec{\\gamma},\\vec{\\beta}$。下面的代码给出了通过量桨构造的损失函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 构造损失函数\n",
    "loss_func = ExpecVal(Hamiltonian(H_D_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 训练量子神经网络\n",
    "定义好了用于 QAOA 的量子神经网络后，我们使用梯度下降的方法来更新其中的参数，使得式（15）的期望值最大。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:12.968989Z",
     "start_time": "2021-04-30T09:11:12.961264Z"
    }
   },
   "outputs": [],
   "source": [
    "p = 4      # 量子电路的层数\n",
    "ITR = 120  # 训练迭代的次数\n",
    "LR = 0.1   # 基于梯度下降的优化方法的学习率\n",
    "SEED = 1024 #设置全局随机数种子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里，我们在飞桨中优化上面定义的损失函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iter: 10   loss: -1.8359\n",
      "iter: 20   loss: -2.5392\n",
      "iter: 30   loss: -2.7250\n",
      "iter: 40   loss: -2.8061\n",
      "iter: 50   loss: -2.8748\n",
      "iter: 60   loss: -2.9134\n",
      "iter: 70   loss: -2.9302\n",
      "iter: 80   loss: -2.9321\n",
      "iter: 90   loss: -2.9321\n",
      "iter: 100   loss: -2.9325\n",
      "iter: 110   loss: -2.9327\n",
      "iter: 120   loss: -2.9328\n"
     ]
    }
   ],
   "source": [
    "paddle.seed(SEED)\n",
    "\n",
    "cir = circuit_QAOA(p)\n",
    "# 使用 Adam 优化器\n",
    "opt = paddle.optimizer.Adam(learning_rate=LR, parameters=cir.parameters())\n",
    "\n",
    "for itr in range(1, ITR + 1):\n",
    "    state = cir()\n",
    "    # 计算梯度并优化\n",
    "    loss = -loss_func(state)\n",
    "    loss.backward()\n",
    "    opt.minimize(loss)\n",
    "    opt.clear_grad()\n",
    "    if itr % 10 == 0:\n",
    "        print(\"iter:\", itr, \"  loss:\", \"%.4f\" % loss.numpy())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解码量子答案\n",
    "当求得损失函数的最小值以及相对应的一组参数 $\\vec{\\gamma}^*,\\vec{\\beta}^*$ 后，我们的任务还没有完成。为了进一步求得 Max-Cut 问题的近似解，需要从 QAOA 输出的量子态 $|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle$ 中解码出经典优化问题的答案。物理上，解码量子态需要对量子态进行测量，然后统计测量结果的概率分布：\n",
    "\n",
    "$$\n",
    "p(z)=|\\langle z|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle|^2.\n",
    "\\tag{16}\n",
    "$$\n",
    "\n",
    "通常情况下，某个比特串出现的概率越大，意味着其对应 Max-Cut 问题最优解的可能性越大。\n",
    "\n",
    "Paddle Quantum 提供了查看 QAOA 量子电路输出状态的测量结果概率分布的函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:55.548009Z",
     "start_time": "2021-04-30T09:11:54.556907Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEWCAYAAABrDZDcAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAY1UlEQVR4nO3dfdhcdX3n8feH8KAFRJCIlgTD1qDGB1ACerVbiwg2VMtDxQqigEJjV7LCpa3EbYuKdhe0stUSW1MRsV0ISK2mNQi2il3dBRKQpwQjEUFCaw0CYuuCpnz2j3MCw2Tue2bu+5y5J/l9Xtc1F3Oevuc7iPO55zz8jmwTERHl2mGmG4iIiJmVIIiIKFyCICKicAmCiIjCJQgiIgqXIIiIKNyOM93AsPbee2/PmzdvptuIiNim3Hjjjffbnt1r2TYXBPPmzWPNmjUz3UZExDZF0j0TLcuhoYiIwiUIIiIKlyCIiChcgiAionAJgoiIwiUIIiIK12oQSFokab2kDZKW9lh+qqRNkm6uX6e32U9ERGyttfsIJM0ClgFHAhuB1ZJW2l7Xterltpe01UdEREyuzRvKDgU22L4LQNIK4BigOwiiIPOWfmnK29593msb7CQitmjz0NC+wL0d0xvred1eL+lWSVdKmturkKTFktZIWrNp06Y2eo2IKNZMnyz+O2Ce7ZcAXwEu6bWS7eW2F9peOHt2z6EyIiJiitoMgvuAzr/w59TzHmf7R7YfrSc/BRzcYj8REdFDm0GwGpgvaX9JOwMnACs7V5D07I7Jo4E7WuwnIiJ6aO1kse3NkpYAVwOzgE/bXivpXGCN7ZXAOyUdDWwGHgBObaufiIjordVhqG2vAlZ1zTun4/17gfe22UNERExupk8WR0TEDEsQREQULkEQEVG4be5RlRExdbmzO3rJL4KIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwrQaBpEWS1kvaIGnpJOu9XpIlLWyzn4iI2FprQSBpFrAMOApYAJwoaUGP9XYHzgSub6uXiIiYWJu/CA4FNti+y/bPgBXAMT3W+yBwPvBIi71ERMQE2gyCfYF7O6Y31vMeJ+llwFzbX2qxj4iImMSMnSyWtANwAfDuAdZdLGmNpDWbNm1qv7mIiIK0GQT3AXM7pufU87bYHXgRcK2ku4FXACt7nTC2vdz2QtsLZ8+e3WLLERHlaTMIVgPzJe0vaWfgBGDlloW2f2x7b9vzbM8DrgOOtr2mxZ4iIqJLa0FgezOwBLgauAO4wvZaSedKOrqt/UZExHB2bLO47VXAqq5550yw7mFt9hIREb3lzuKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCjdQEEj6FUm71u/fLOkCSc9pt7WIiBiFQX8R/DnwU0kHAu8Gvgt8trWuIiJiZAYNgs22DRwDXGh7GbB7e21FRMSo7Djgej+R9F7gLcCvStoB2Km9tiIiYlQG/UXwRuBR4G22fwDMAT7SWlcRETEyAwVB/eX/N8Au9az7gb9tq6mIiBidQa8a+h3gSuCT9ax9gS+01FNERIzQoIeGzgB+BXgYwPadwDPbaioiIkZn0CB41PbPtkxI2hFwOy1FRMQoDRoEX5f034CnSjoS+Bzwd+21FRERozJoECwFNgG3AW8HVgF/2G8jSYskrZe0QdLSHst/V9Jtkm6W9A1JC4ZpPiIipm+g+whsPwb8Zf0aiKRZwDLgSGAjsFrSStvrOla71PZf1OsfDVwALBp0HxERMX2TBoGkK2z/tqTb6HFOwPZLJtn8UGCD7bvqWiuo7kx+PAhsP9yx/q699hEREe3q94vgzPqfr5tC7X2BezumNwIv715J0hnAu4CdgcOnsJ+IiJiGSc8R2P6X+u07bN/T+QLe0UQDtpfZ/iXgbCY47yBpsaQ1ktZs2rSpid1GRERt0JPFR/aYd1Sfbe4D5nZMz6nnTWQFcGyvBbaX215oe+Hs2bP77DYiIoYxaRBI+i/1+YHnSbq14/U94NY+tVcD8yXtL2ln4ARgZVf9+R2TrwXuHP4jRETEdPQ7R3ApcBXwP6guId3iJ7YfmGxD25slLQGuBmYBn7a9VtK5wBrbK4Elko4Afg48CJwyxc8RERFT1C8IbPvu+oTuk0jaa4AwWEV1z0HnvHM63p+51UYRETFSg/wieB1wI9WlnepYZuA/tdRXRESMyKRBYPt19T/3H007ERExav1uKHvZZMtt39RsOxERMWr9Dg19dJJlJjeARURs8/odGnrVqBqJiIiZ0e/Q0OG2vyrpt3ott/35dtqKiIhR6Xdo6NeArwK/2WOZgQRBRMQ2rt+hoffV/3zraNqJiIhRG/Th9c+Q9HFJN0m6UdLHJD2j7eYiIqJ9gw46t4LqCWWvB46v31/eVlMRETE6Az2hDHi27Q92TH9I0hvbaCgiIkZr0F8E10g6QdIO9eu3qQaTi4iIbVy/y0d/whNjDJ0F/HW9aAfg34Dfa7O5iIhoX7+rhnYfVSMRETEzBj1HgKQ9gfnAU7bMs/1PbTQVERGjM1AQSDqd6kH2c4CbgVcA/5eMNRQRsc0b9GTxmcAhwD31+EMvBR5qq6mIiBidQYPgEduPAEjaxfa3gee111ZERIzKoOcINkp6OvAF4CuSHgTuaaupiIgYnYGCwPZx9dv3S/oasAfw5da6ioiIkRnmqqGXAf+Z6r6Cb9r+WWtdRUTEyAw66Nw5wCXAM4C9gYsl/WGbjUVExGgM+ovgJODAjhPG51FdRvqhlvqKiIgRGfSqoX+m40YyYBfgvubbiYiIUes31tCfUZ0T+DGwVtJX6ukjgRvaby8iItrW79DQmvqfNwJ/2zH/2la6iYiIkes36NwlW95L2hk4oJ5cb/vnbTYWERGjMehYQ4dRXTV0N9WQ1HMlnZJB5yIitn2DXjX0UeA1ttcDSDoAuAw4uK3GIiJiNAa9aminLSEAYPs7wE7ttBQREaM06C+CGyV9iieeUHYST5xIjoiIbdigQfC7wBnAO+vp/w18opWOIiJipPoGgaRZwC22nw9cMExxSYuAjwGzgE/ZPq9r+buA04HNwCbgbbYzqmlExAj1PUdg+z+A9ZL2G6ZwHSDLgKOABcCJkhZ0rfYtYKHtlwBXAh8eZh8RETF9gx4a2pPqzuIbgH/fMtP20ZNscyiwwfZdAJJWAMcA6zq2/1rH+tcBbx6wn4iIaMigQfBHU6i9L3Bvx/RG4OWTrH8acNUU9hMREdPQb6yhp1CdKH4ucBtwke3NTTch6c3AQuDXJli+GFgMsN9+Qx2hioiIPvqdI7iE6gv6Nqpj/R8dovZ9wNyO6Tn0GLFU0hHAHwBH2360VyHby20vtL1w9uzZQ7QQERH99Ds0tMD2iwEkXcRwI46uBuZL2p8qAE4A3tS5gqSXAp8EFtn+4RC1IyKiIf1+ETw+sNywh4Tq9ZcAVwN3AFfYXivpXElbTjJ/BNgN+JykmyWtHGYfERExff1+ERwo6eH6vYCn1tMCbPtpk21sexWwqmveOR3vjxi+5YiIaFK/YahnjaqRiIiYGYMOOhcREdupBEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhWs1CCQtkrRe0gZJS3ssf6WkmyRtlnR8m71ERERvrQWBpFnAMuAoYAFwoqQFXat9HzgVuLStPiIiYnI7tlj7UGCD7bsAJK0AjgHWbVnB9t31ssda7CMiIibR5qGhfYF7O6Y31vMiImKMbBMniyUtlrRG0ppNmzbNdDsREduVNoPgPmBux/Scet7QbC+3vdD2wtmzZzfSXEREVNoMgtXAfEn7S9oZOAFY2eL+IiJiCloLAtubgSXA1cAdwBW210o6V9LRAJIOkbQReAPwSUlr2+onIiJ6a/OqIWyvAlZ1zTun4/1qqkNGERExQ7aJk8UREdGeBEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4BEFEROESBBERhUsQREQULkEQEVG4VoNA0iJJ6yVtkLS0x/JdJF1eL79e0rw2+4mIiK21FgSSZgHLgKOABcCJkhZ0rXYa8KDt5wL/Ezi/rX4iIqK3HVusfSiwwfZdAJJWAMcA6zrWOQZ4f/3+SuBCSbLtNhqat/RL09r+7vNe21AnW5tOb919NVlrnOVz9rctfc6YOWrpOxdJxwOLbJ9eT78FeLntJR3r3F6vs7Ge/m69zv1dtRYDi+vJ5wHrW2ka9gbu77vW6Gs1Xa+EWk3XK6FW0/VKqNV0vaZ76/Qc27N7LWjzF0FjbC8Hlre9H0lrbC8ct1pN1yuhVtP1SqjVdL0SajVdr+neBtXmyeL7gLkd03PqeT3XkbQjsAfwoxZ7ioiILm0GwWpgvqT9Je0MnACs7FpnJXBK/f544KttnR+IiIjeWjs0ZHuzpCXA1cAs4NO210o6F1hjeyVwEfBXkjYAD1CFxUxq8vBT04eyxrW3ca3VdL0SajVdr4RaTddr/RB4L62dLI6IiG1D7iyOiChcgiAionAJgoiIwiUIIiIKt03cUNYWSaIaCmPfetZ9wA1NXsIq6fm2vz3kNnsAi7r6utr2Qw32daTtr0xhu7HsTdLzqYYs6exrpe07GuzrrbYvbqpexLgo9qohSa8BPgHcyRM3us0Bngu8w/Y1De3n+7b3G2L9k4H3Add09XUk8AHbn52Jvsa5N0lnAycCK4CNHX2dAKywfd5M9NWx3ViGZ73dWAboKPqaRm+/Dhzb1dsXbX+5wb7OsX1uU/X67q/gILgDOMr23V3z9wdW2X7BELU+PtEi4BTbTxui1nqq8ZYe6pq/J3C97QOGqNV9A19nX4fb3nXQWuPcm6TvAC+0/fOu+TsDa23PH6LWrZP0dYDtXQatVdcby/CstxnLAB1VX1Ps7U+BA4DPdvV2MnCn7TNnoq/pKvnQ0I488T9kp/uAnYas9Vbg3cCjPZadOGQtAb3S+bF62TB+FXgz8G899nHokLW2bDeOvT0G/CJwT9f8Z9fLhrEP8OvAgz36+j9D1gL4A+DgicKT6gtlIH3C8xlT6O00egfoBcBaYOAv3D4Bus9M9dVCb7/R6w8eSZcD3wEGDgJJD0/S11OH7GtaSg6CTwOr6+Gx763nzaX6q+OiIWutBm63vdUXhaT3D1nrj4GbJF3T0dd+VH9BfnDIWtcBP7X99R59TWUE13Ht7SzgHyXd2dXXc4ElE200gb8HdrN9c4++rh2yFoxveG7pYRwDtMm+mu7tEUmH2F7dNf8Q4JEhaz0EHGL7X7sXSLp369XbU+yhIYD6QTlHs/VxyHUTb9Wzzl7AI7Z/2lBfe1L9h9t9TLn7P+SRG9feJO3A1if+V9v+j5nrCiSdApxDdWhoq/C0/Zkhal0FfNj213os+yfbrxyyt0XAhVTnybYK0GGOeUu6CLjY9jd6LLvU9ptmoq8WensZ8OfA7jxxRGEu8GPgDNs3DlHrQ1TfNzf0WHa+7bMHrTVdRQfBFvUXObYfGKda40rSPnR84fb6i2Ymak1Qfzfb3X9Bj7TWuIYnjHWAjmVfW0h6Fk/+7/YHM9nPdBUbBJL2Az4MHE6V5gKeBnwVWNp9EnnAWq+m+rk35Vp99nOb7RfPVC1JBwF/QTVc+EaqzzmH6jO/w/ZNQ9R6KdVfVnvw5JOoQ9fqs5/GTrpNp9a2FJ71PmY0QJu+tHtcLxUfRa1BlHyO4HLgT4GTtvyVoeo5y2+gulrhFTNRS9JvTbQIeNYQPTVaq/YZ4O22r+/azyuAi4EDh6h1cVO1JL1rokXAbkP01Gitut5B9AhPSQ/RUHhOpdYA1lEdjhl5rcku7ZY09KXdTdebxDU09++syVp9lRwEe9u+vHNG/SW+QtKwJz6brHU58L/ofYLxKTNYC2DX7i9uANvXSRrqUtSGa/134CPA5h7Lhr17vslaMKbhWW83rgH6MeCIiS7tBga+tLvpen0uFX/6ME01WWu6Sg6CGyV9AriEJ181dArwrRmsdSvwJ7Zv714g6YgZrAVwlaQvUV3y2Pk5TwaGvZmmyVo3AV/odaJO0ukzWAvGNzxhfAO0yUu7m67X5KXiTdaalpKD4GSq65U/QNdVQwx/+WiTtc4CJrq++LgZrIXtd0o6iq3v+Fxme9VM1aL6P9REjzgd9vmvTdaC8Q1PGN8AbfLS7qbrNXmpeJO1pqXYk8URozJB4K2cQuA1Xet5wAO2N/VYts8wJ6GbrFVv8wJ6f86hLu1uul6Tl4o3fdn5tHopNQgk7Uj1V/yxdI0ZAlzUfVfjDNQ6juqmmrGoNcC+lttenFoR256Sg+AyqksVL+HJY4acAuxl+42ptVW9vSZaBNxie05qbVVvD+C9VH+N7kN14v6HVGF8XvfQE6Oq1VXvWOCZDfU27Vp99nOV7aOaqNV0vXGtNYiSzxEc7K3HDNkIXKdqELPU2tomqtv+O4dGcD39zNTq6Qqq+0leteWmo/pmpFPrZa+ZoVqd9Q7rqnfKNHqbdq367t2ei4CDhuip8XrjWmu6Sg6CByS9Afgb24/B43czvoGtxyRJrcpdwKttf797gYYfG6WEWgDzbJ/fOaP+ojxP0ltnsNZk9c6X9LYZrLUa+DpPDuMtnj5krabrjWut6bFd5AuYR3Wd/Q+pRg38Tv3+cmD/1OpZ7wzgwAmW/dfU6rnNNcB7gH065u0DnA38w0zVGufegNuB+RMsu3cKn7OxeuNaa7qvYs8RwIRXEnzRU3j4RQm16nqNPTCkkFp7AkvrelsOLf0r1aXF53mI8YaarDXOvUk6HrjN9laj0Eo61vYXBq3VdL1xrTVdxT6zWNXDLy6lOv57ff0CuEzS0tTqWe89VENmCLihfmmKvW33tQBsP2j7bNvPt71X/XqBq5Elj52pWuPcm+0re3051vYcplbT9ca11rSN8ufHOL2oDpPs1GP+zlRPGkqtbaS3ca01wL6+P461xrm3fM52XiWfLG7y4Rcl1Brn3sa1Fmrw6VhN1mq63rjWarreuNaarpKD4Cyae6pVCbXGubdxrQXNPh2r6cdojmtv+ZxT+5xTVmwQ2P6ypANo4OEXJdQa597GtVatyUdfNv0YzXHtLZ9zap9zyoq+aigiIgq+aigiIioJgoiIwiUIYrsmaY6kL0q6U9Jdki6UtMsA2/V8xq6kc1U/1EfSWZJ+YYL1XifpW5JukbRO0tvr+cdKWjDA/gdaL6IJCYLYbkkS8HmqB6bMB+YDTwU+PNWats+x/Q/15FnAVkEgaSdgOfCbtg8EXgpcWy8+FhjkC37Q9SKmLSeLY7sl6dXA+2y/smPe06juEZgLHA8stL2kXvb3VI/2vLb+RfCXVKNm/gA4wfYmSZ+hutrjF4E/AdYD99t+Vcc+9gK+DTzH9v/rmP/L9bY/rl+vBw4HFlPdsLYBeAvVyJPd6wEsA2YDPwV+x/a3G/kXFcXLL4LYnr0QeNKjE20/DNxNdV/AZHYF1th+IdUIke/rqvNx4J+phoR+VdeyB6jG2LlH0mWSTpK0g6tHEq4Eft/2Qba/C3ze9iH1L4c7gNMmWG851aB3BwO/B3xi6H8bERMo9j6CiD4eoxqlFeCvqQ4xDcz26ZJeDBxB9cV9JNVzA7q9SNKHqIYd3g24unsFSbsBvwx8rjraBUDf8xwRg0oQxPZsHdXhn8fVh4aeRXVI50U8+VfxUyapNfQxVNu3AbdJ+ivge/QOgs8Ax9q+RdKpwGE91tkBeMj2QcP2EDGIHBqK7dk/Ar8g6WQASbOAjwIX1sfu7wYOkrSDpLlUdxNvsQNPhMibgG/0qP8TYPfumZJ2k3RYx6yDeGLsou5tdgf+pT7BfFKv2vXhrO+pesgQqhw42QePGEaCILZbrq6EOA44vh476EfAY7b/uF7lm1R/qa8DPg7c1LH5vwOHSrqd6oTuuT12sRz4sqSvdc0X8B5J6yXdDHyAJ34NrAB+v7609JeAP6IaHvybVCeYmWC9k4DTJN0CrKUa9z+iEblqKIpRX7VzGXCc7Zv6rR9RigRBREThcmgoIqJwCYKIiMIlCCIiCpcgiIgoXIIgIqJwCYKIiMIlCCIiCvf/AZ7B8yt2B+AWAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "state = cir()\n",
    "# 模拟重复测量电路输出态 1024 次\n",
    "prob_measure = state.measure(shots=1024, plot=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过测量，找到出现几率最高的比特串。 此时，记其在该比特串中对应的比特取值为 $0$ 的顶点属于集合 $S_0$ 以及对应比特取值为 $1$ 的顶点属于集合 $S_1$，这两个顶点集合之间存在的边就是该图的一个可能的最大割方案。\n",
    "\n",
    "下面的代码选取测量结果中出现几率最大的比特串，然后将其映射回经典解，并且画出对应的最大割方案：\n",
    "- 红色顶点属于集合 $S_0$，\n",
    "- 蓝色顶点属于集合 $S_1$，\n",
    "- 虚线表示被割的边。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:55.906817Z",
     "start_time": "2021-04-30T09:11:55.625551Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "找到的割的比特串形式： 0101\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAArzElEQVR4nO3deXQUVdoG8Kc7a3cIaTYhCYu4gEMQUEA0AuHzIAok4AwDqOxRNh0QEcUZFJhx/BQEZHFkU3YVhHEhyOIoiElw2D6RTRIiIAaiYCCRLJ2t7/fHtZskZK/qruqu53dOzkl3kqpXTPrpW/ete01CCAEiIiKDMGtdABERkScx+IiIyFAYfEREZCgMPiIiMhQGHxERGQqDj4iIDIXBR0REhsLgIyIiQ2HwERGRoTD4iIjIUBh8RERkKAw+IiIyFAYfEREZCoOPiIgMhcFHRESGwuAjIiJDYfAREZGhMPiIiMhQGHxERGQoDD4iIjIUBh8RERkKg4+IiAyFwUdERIbC4CMiIkNh8BERkaEw+IiIyFAYfEREZCgMPiIiMhQGHxERGQqDj4iIDIXBR0REhsLgIyIiQ2HwERGRofhrXQCREdjtwNGjwOHDwIULwLVrQHExEBICNGgAdOwIdO4MNG2qdaVEvo/BR+QmR44Ab70F7N4N/PQTYLXKsMvLK/t9/v4yAO12+T133QXExwN//jMQFKRJ6UQ+zSSEEFoXQeQr7HZgyxZgzhzgzBmgoAAoKan9cerVA0wmYPx44C9/AVq1Ur9WIqNi8BGpZNs2YNQooLAQyMlR55iBgYDZDIweDcybJ0eGRKQMg49IoatXgXHjgO3bb7yMqRaLBbDZgE2bgB493HMOIqNg8BEp8OWXwODBMvAKCtx/PotFzv8tWgT4+bn/fES+iMFHVEdbtgAjRwL5+Z49r9UK9OoFfPQRm1+I6oLBR1QHH34o5908HXpOFgsQHQ3s2AEEBGhTA5G3YvAR1dLnnwOPPKJd6DlZLEDfvnLkaTJpWwuRN+HKLUS1cPkyMGSI9qEHyBp27QJWrtS6EiLvwhEfUS3ExgL/+Y+8ZUEvQkKAkyeBli21roTIO3DER1RDmzcDe/boK/QA2U362GMA38IS1QyDj6gGrl0Dxo513316ShQXA999B6xbp3UlRN6BwUdUA+vWyYDRq9xc4JVXOOojqgnO8RFVQwigdWvgxx+1rqRqISFy/vG++7SuhEjfOOIjqkZiIvDrr8qP07s3sGAB8NVXQHa2DFTnR0yM8uPn5cn1PImoatyWiKgaCxaoM7f39NPy/j93EUKuF3rlCtCwofvOQ+TtOOIjqkZiojpzZ0LITWgTEoD33lN+vIoEBgIHDrjn2ES+gsFHVIVLl2TjiBqGDQOaNwcGDHDfTed5ecDBg+45NpGvYPARVeHwYSA4WJ1jeWK1l+JiYO9e95+HyJsx+IiqcPCgeiM+TzlyROsKiPSNwUdUhdRUfd+/V5HMTMDh0LoKIv1i8BFVwdtGe4DcoNYTm+ISeSsGH1EVioq0rqD2zGbvrJvIUxh8RFWwWLSuoPaKi72zbiJPYfARVaFBA60rqD2zGfDn0hREleKfB1EVOneWN5ursXLLkCFA167y8xYtyn5t4kS51x8gO0k//LDu52ndmjuyE1WFwUdUhc6d1Rs99e0LjB5d8deGDr3++Zo1yoKPi1QTVY2XOomqcOednrnxXC1WK9C9u9ZVEOkbtyUiqsbttwNpaVpXUTOhoXKX+M6dta6ESL844iOqxvDh6i1b5m5BQUCnTlpXQaRvDD6iaowf7x07m1sswJQp8gZ2Iqocg4+oGs2aAQ8+qP9OSYcDGDtW6yqI9I/BR1QDzz8vG0f0ymwG+vUDbrpJ60qI9I/NLUQ1IATQo4fAN9844HDo71qixQJ8+y3Qtq3WlRDpH0d8RDVw+nQq7PY/weHQ370NISHAjBnFOHp0M/g+lqh6DD6iKpSUlGDBggXo2LEjDh/+BPXrz0JwsH72KTKbgVtvBXJyZmPIkCGIjY3FhQsXtC6LSNcYfESVSElJQc+ePfHcc8/Bbrdj1KhROHv2Jdxzjz+CgrSuTgoOlqu8tG//B9hsNmzfvh1RUVFYs2YNR39EleAcH1EFCgoK0Lp1a2RkZCAiIgIrVqxA//79AQDZ2cA99wBnz2q7/Y/FAnz0EfDww/LxxYsXMX78eGzbtg0A0K9fP6xYsQKRkZHaFUmkQww+okqsXbsWe/bswZtvvokG5bZpuHQJuPdeID1dm/CzWIC1a4HBg8s+L4TAhg0bMHnyZGRlZSEsLAyHDh3Cbbfd5vkiiXSKwUcEOZe3aNEiBAQEYNKkSTX6mStXgJgY4IcfPLeep8kkQ2/zZnn7QmWco7+SkhJ89tlnMOn9JkQiD2LwkeGlpqZizJgx2LdvH4KDg3HmzBmEh4fX6Gfz84EXXgDefdf94We1yu2MNm+Wi2dXRwiBvLw8hISEAJBzlvv27cPo0aMZhGRobG4hwyrdsblv3z6Eh4dj8+bNNQ49QI6+liwBvvgCiIx0z87nzlHeCy8Ax47VLPTkz5lcoVdSUoL4+HjEx8ez85MMj8FHhpSamlqmY3PkyJE4ceIEYp27wdZSdDRw+jQwebLcIaFePeU1BgbKrs1evYD9+4FZs4CAgLody2w2Y8KECez8JAIvdZJB9e7dG19++SXCw8OxYsWKOgdeRQoKgC1bgDlz5PwfUPMd3P395SVNIYAJE4CnnwZatVKtNHZ+EoHBRwYihHDNbaWmpmLu3Ll44403bujYVNPJk0ByMpCUBHzzDXDunAy3/PwcAAJWayiKioCwMOCuu+TorksX2TTjrnsFy3d+NmvWDGfOnIHFHddpiXSIwUc+z9mxmZycjC1btmja2FFYCGRmAhERtwDww/nzp1G/vgw+T3OO/nr16oXnnnvO8wUQaYTBRz6tdMcmAHz11VeIiYnRuCq4wlfrPz8hBIQQMJvldP8HH3wAu93Ozk/yaWxuIZ9UUcdmQkKCLkJPT0wmkyv0Ll++jIkTJ7Lzk3weg498jtodm0bRuHFjLFmypEzn5+rVqzUflRKpjcFHPmfDhg1lRnlr1651awOLrzCZTBgxYgROnjyJuLg4ZGdnc/RHPolzfOQTCgsLERgYCEAuMP2Pf/wD06ZN023g6WWOrzLlOz/vv/9+JCUlaV0WkSoYfOTVnB2bb731Fg4dOoSGDRtqXVKN6D34nDIyMvDUU09hxowZ6NKli9blEKmCwUdeq3zH5vLlyzFu3DiNq6oZbwm+ikyaNAmdO3fGqFGj2PlJXonBR17HOcqbMWMG7Ha7W1ZfcTdvDb5vvvkG0dHRALjqC3kvNreQV2HHprbuvfderFu3jmt+kldj8JFXSU9PZ8emhpydn843G9nZ2RgzZgw7P8mr8FIn6V5mZiYaNWrkerx+/XrExsZ6deB566XO0sp3fk6ePBmLFi3SuiyiajH4SLecc3kvv/wyduzYgZ49e2pdkmp8IficMjIyMGvWLMybNw/169cHUHZBcCK94aVO0qXSc3l5eXnYtWuX1iVRJZzNRc7Qy8vLQ7du3Tj3R7rF4CNdqWyNzVdffVXr0qiG3nvvPRw8eJBzf6RbvNRJunHu3DkMGzbMdV/eyJEjsXDhQq+ey6uML13qLK/83F9YWBgWLlzI+/5INxh8pBuXL19GVFQU/P39ve6+vNry5eBz4m7vpFcMPtJUWloaWrVqhYCAAADA/v370aZNG58c5ZVmhOADbhz9bdq0CUOGDNG6LDI4zvGRJpxzeXfeeSdee+011/PdunXz+dAzktL3/c2dOxeDBw92fS0/P1/DysjIGHzkceVXX/npp598fuRjdBEREXj++eddI92jR4+iVatW3O+PNMHgI4+prGNz5cqVbHowmPfeew+XL1/mfn+kCc7xkUdcvXoVsbGxhujYrAmjzPFVpqLOzzfffBOjR4/mmyByO474yCNsNhssFgvX2CQAVe/2fvHiRa3LIx/HER+5TWpqKgIDA3HzzTcDkO3tFouFgQeO+EorPforKirCsWPH0Lp1a63LIh/G4CPVld4vr1u3bti9ezfMZl5cKI3Bd6OMjAwcOXIEffv2BQA4HA5cunQJzZo107gy8jV8NSJVle/YbNWqFex2u9ZlkRcIDw93hR4ALF26FHfccQc7P0l1DD5SRWUdm2vXroXVatW6PPJCycnJZeb+2PlJauGlTlLM4XCgd+/e2LNnDwB2bNYEL3VWj52f5C4c8ZFiZrMZvXv3Zscmqaqyzs/+/fvjypUrWpdHXowjPqqT1NRUnDt3Dn369AEAFBcX49q1awy8GuKIr3ZKj/5uueUW/Pe//3Wt70pUWww+qpXSHZtWqxUnTpxg110dMPjqJiMjAzk5Obj99tsBAJcuXUJRURF3fKBa4aVOqrHyHZuxsbEICgrSuiwykPDwcFfoCSEwceJEREVFcbd3qhUGH1Wrqo5NXtokrdjtdhQWFiI7O5u7vVOtMPioWvHx8a5R3siRI3HixAmf3iSWvIPFYsHWrVuxbt062Gw2bN++HVFRUbzvj6rFOT6q1r59+zB06FAsXbqUgacSzvGpq/xu7/3798enn34KPz8/jSsjPeKIj26QkpKCefPmuR5HR0cjLS2NoUe6FRERUWb016ZNG4YeVYojPnIpKSnBwoUL8dJLL8Fut2PXrl2u2xVIXRzxuU9GRgbCwsJcKwYdPHgQERER7PwkF474CIAc5fXs2RPTpk2D3W7HqFGj0LVrV63LIqq18PBwV+j99ttvGDRoEDs/qQwGn8GVlJRg/vz56NSpE/bt24eIiAhs27YNa9asYccmeb2CggJ07NiRnZ9UBoPP4F5//fUyo7zjx4+jf//+WpdFpIomTZpU2PnJ0Z+xcY7P4LKystCnTx/MmjWLgedBnOPzvPKdn0888QTeeecdjasiLXDEZzCpqakYPXq0a488m82G/fv3M/TI55Xv/PzjH/+odUmkEQafQZSUlODNN99Ex44dsXbtWsyZM8f1NW7xQkbh3PHh7NmzZd7srV+/nnN/BsLgM4DU1FTExMRg6tSprtVXJk+erHVZRJqx2Wyuzw8cOIDRo0dz7s9AGHw+rPQoLzk5GeHh4di6dSvX2CQqpUWLFujfvz87Pw2EzS0+bNu2bYiLiwPAXdH1hs0t+lLRbu8LFy7EqFGjOBXggxh8PkwIgfHjxyMuLs4VgKQPDD59Kt/5+corr+Cll17SuCpSG4NPDcXFQH4+YDIBFgug0RqBqampmDhxIpYsWYJ27dppUgPVDINPv5yjv9mzZyMxMRERERFaFwTY7UBhIRAUJD84ClWEwVdbp08DBw4A33wDJCUBp07JX0hn2BUXA1YrEBUF9OwJdOsmP1q2dFtJpXdFt9vtGDhwID755BO3nY+UY/DpX3FxMfz9/QHIv7EXX3wRzzzzDJo3b+6+k+bmAgcPAocOAV99BRw+DPzyC2A2yw+HQ35ERgJduwIxMUDnzkCXLkBwsPvq8jWCqpeXJ8Tq1ULccYcQFosQ9eoJId+HVf1hNgsRGipEcLAQXbsKsWWLEIWFqpaWkpIioqOjBQABQIwcOVJcuXJF1XOQ+pz/v8g7LFiwQAAQYWFhYtWqVcLhcKh7ghMnhBg7Vr6+1K8vRGBgzV5jgoLk99erJ8Qzzwjxww/q1uWj+JdXlStXhJg8Wf5S1TTsqvoIDRXCZhNi5kwZpgoUFxeL+fPni+DgYAFAhIeHi4SEBJX+w8ndGHze5eLFiyIuLs71/61fv34iPT1d+YF37RKic2cZeP7+yl5fAgLkm+wePYRISlJemw/jX15ltm4VokED+Y5KaeCV/7BYhIiMFCI5uc7lnT17VlgsFo7yvBSDz/s4HA6xbt06YbPZlI/+rl4VYuhQIaxW9V9fnK8xEyYIkZur+r+DL+AcX3lXrwLjxgHbtwN5ee49l8UCxMcDb7whP69GSUkJzGaza35o9erVaNKkCTeI9UKc4/NeGRkZGD9+PBISEgAAW7ZswaBBg2p+gO3bgREj5HxeQYGbqoR8TbHZgE2bgB493HceL8TgKy0tDbj/fiA7272/kKVZLECLFkBiInDTTZV+W2pqKsaMGYMxY8bgySef9Ext5DYMPu8mfu/83Lx5Mz7++OOa7fYuBPDyy8Cbb7r/TXVpFgvw+usAV2tyYfA5HT8u3xVlZ8tfUE8KCACaNgX++1/ZrVVK+Y7NO+64A8ePH6/ZHxrpFoPP96Snp2PatGmYP3/+jbu9CwH85S/AmjWeDT0nqxWYPh2YOdPz59YhLlkGAD/8IG89yMryfOgBQFERkJEBREcDly+7nk5NTUXPnj3x3HPPudbY3LdvH0OPSIemTZuGTZs2Vbzm5/Tp2oUeIM87Zw4wb54259cbjeYW9ePaNSEiIuStB+6YZK5tV1aHDqLYbmfHpo8Dm1t8zoULF0RsbOyNnZ8rVriviaW2H1arEB9/rPU/leZ4qTM+HvjgA7kygh6EhKB4+nR03rIFR48e5RqbPoqXOn2TEGXX/GwfGor/KyhAQGGh1qVdZ7PJfoZGjbSuRDPGDr7du4G4OO0uP1TGYsH3Gzbgh8BAdmz6KAafb8vIyMD4cePw4rZt6AogQOuCSgsMBPr2BQy8upNxg+/aNeC224BLl7Su5EYmE9CuHXDkCPD7kknkWxh8vk8sXYriZ59FgKc6xGvDagU2bAAMugu9cZtbliyR4adHQgDnzgFbtmhdCRHVhd0O0/Tp+gw9QF7levppue6nARkz+EpKgIUL5Y4KepWbC8ydq3UVRFQXW7Zo0yFeG9euAV98oXUVmjBm8O3cqZ9mlqqcOiXvLyQi7zJnDpCTo3UVVcvJMeyba2MG39y5yi9z2mzAyJHAO+/IrUMuXJCrvWRnyy1F/v53QGknZmGhXOWBiLzHt98CZ84oP07DhsCrrwJHj8rXq2vX5Oevvqr8tcUpORk4f16dY3kR4zW3XLsm23iLipQdZ9Cg6ufgLl4EHngASEmp+3nq1QN++40bT/oYNrf4sOnTgfnz5ZRKXUVFAZ9/DlS2Ce7Fi0CfPsCJE3U/ByD38Pvf/wWefVbZcbyM8UZ8334rO5rUkpUFbNwo1+CbN0/+QjpFRADLlys7fkmJId+REXmtvXuVhV5wMPDRR9dD7+pVeZVqzhz5OSC/9u9/y93YlbDbZb0GY7xe+cOH1Znfu3IFeOYZYOXKsk0yc+bIebmmTeXjHj3kqK2u1/sDAmTNrVopr5mI3EsI5fPyw4YBbdpcf/z447IvAZAhtX27/LxtW/m9q1YpO9+hQ8p+3gsZb8S3d686Oy/s2QMsXnxjZ+ivv8qdFpzMZnnDaF3l5MjFq4lI/86fV36LQOl767Kzr4ceID//7bfrj//0J2XnAuS9zHq9tctNjBd8337r/nPcccf1z9PS5OiwrhwO4JtvlNdERO733XfyKo0SnTpd//zs2bJfE6Lscx07KjsXIKd+DNY9brzgc3eL8cyZQPv2ZR8rlZ2t/BhE5H7Z2cpHfKXX0Cw9uqvoucaNlZ2rqvP4MOPN8blrsViTSTa3TJ16/bnZs+UC2ErpdfUHIirLbld3NZSKurnV7vAWwjvua1aR8YLP7IZBbr16MuCcC0o7HMALL8iWZjVw/z0i7+DnpzyYMjOvb0hdv/6NXy/93K+/KjsXIOs12GuM8YJPaftveS1bAgkJQIcO8nFuLjBiBPDxx+qdIzhYvWMRkftYLMrfXB85cj34WreWweS839Nkks85ffedsnM5WSzqHMdLGG+Or1kz9Y7VrRuwf//10PvpJ6B7d3VDD5DhSkT6FxmpfMRXerug+vXlFkJOffsCoaHXH6vxWlNSUvmN8j7KeCu3PPUUsHSp8uPcdx/w5ZfX3ykVF8uFr3/++cbv3bQJSE+v23mCgoDXXjPcygq+jiu3+Cg1VoYKDpYjOee9fFlZ1xfCGDfu+nJlqamyq1Pp/FxQkLxSZaDLnca71HnffcD69cq7O9u0KXt5wN8fmDat4u89dKjuwRccDHTuXLefJSLPCg0FmjQpu4JTbdnt8v68//wHCA+X6wJPn172ezIy5Peo0ZTSpo2hQg8w4qVObwuRvDzgrru0roKIaqpLF+XHOHFC3hb12mvy89xc+XHihHyufXvl63Q6de+uznG8iPEudZaUyHdQet8yxOnWW+VN8ORTeKnThy1dKq/+5OVpXUn1QkPlkmd//rPWlXiU8UZ8fn7AE08oX13BE0JCOLdH5G0ee8x7djY3mYC4OK2r8DjjBR8ATJrkHde0HQ55awQReQ+bTW5bpvfXmMBAYPx49W/x8gLGDL5bbwW6dtW6iqr5+wOPPlrxDaxEpG9Tp+o/UMxm4Omnta5CE8YMPgCYMUNeStSrgADguee0roKI6uLuu4G2bSH0uoG0vz/Qq5dhtzszbvA99BDQu7eyLYPcJA/AyZgYiHbttC6FiOrox1dfRYFegy84WO4lalDGDT4AeOcd3S3V4wBwCcBdO3diwIABuKjkfiAi8jiHw4FFixbhD4MG4R8OB3K1Lqi8kBC52Ebz5lpXohljB1/jxsDq1XI/Kp0wWSw4/vLLsISFYdu2bYiKisL69evZ9k7kBdLS0tCrVy9MmTIF+fn5SH/sMQTdcYf6OyrUlb+/vJc5Pl7rSrQlSIgxY4SwWoWQS8Fq92G1CvHKK0IIIdLT00W/fv0EAAFAxMbGiszMTI3/oUgtzv+v5DvefvttYbFYBADRtGlT8cknn8gvpKQIUb++9q8vJpMQjRsLkZ6u7T+UDhh7xOe0ciXw4IPaXva0WuX9hTNmAAAiIyOxbds2rF69GmFhYTh37hxC9NyMQ2RweXl5yM/Px7Bhw3Dy5EkMHDhQfqFNG2D3bm2b6UwmICwMSE6+vvODgRlv5ZbKFBXJ2wd27vT8igtWKzBhgtzItoJLIhcuXEB2djba/d7scuXKFRQUFCA8PNyzdZJquHKL93M4HDh16pTr77KkpAR79+7FAw88UPEPHDgg32B7erdzs1neW5iYCLBhDoDR5/hKCwgANm8GnnzScyM/k0mea/ZsuWltJfMAkZGRrj8uAJg0aRLatWvHuT8ijaSlpSEmJgbR0dG4cOECAMDPz6/y0AOAe+65PuLy1GuM1Qrccgtw+DBDrxQGX2lmM7BokRz1hYe795fTapWXQPbvB55/vsY/VlBQgKtXryIrKwsjR47EwIED2flJ5CHOjs0OHTogKSkJwcHBOHfuXM0P0L693E4oPt69ry/ON9VTpwInTwI33+y+c3kjbacYdSw3V4gJE4SwWIQICFBvgjkoSB5z9mwhCgvrVJrD4RCrVq0SYWFhAoCw2Wxi3bp1wuFwqPyPQO4CNrd4ndOnT4vu3bu7/t8NGzZMWcNZcrIQkZFC1KunbhNLvXpC3H67EEeOqPcf72P4l1edlBQhnnpKiJAQ+VHXX8bQUCFsNiH+9jchfvpJldJ++ukn0bdvX9cfYlxcnCgqKlLl2OReDD7v8v7771fcsalUQYEQGzcKcddd8g2xn1/dXl8CAoQIDhYiOlqITz8Vgq8DVeKlzuq0aQP861/ApUvyMujdd8s1+EJC5JYeFc3Lmc1yjU2rVX7cf7+8Wf7SJeDVV1W7cbR58+b47LPPsGrVKoSFhaF58+bw9zfe3sJE7nb77bejsLDwxo5NpQIDgaFDgf/7P9n8MmqUnGYJCJBdmJWt9xkcLF9j/P2BFi3kYtNHj8o5xAED5PNUKXZ11oXDAZw+LSeMDxwAfvlFbhJpMslAbN5cTmR37iyvrXvg5tX09HTYbDbUq1cPAHDkyBHcdNNNiIiIcPu5qfbY1alvDocDn3/+OR5++GHXcykpKWjbtq1nCsjOBr79Vr7GHD0q9w8tKLgeeB07yteXTp2A3//mqeYYfD4oNzcXHTp0wJUrV7B48WIMHz7c9UJL+sDg06+0tDTEx8cjMTERW7duRZwB96vzdbzU6YPy8vLQtm3bMp2fGRkZWpdFpGulOzYTExPRtGlTTh34KAafD2rSpEmZub+EhATe90dUhfJrbDrn8vr27at1aeQGvNTp49LT0zFu3Djs2LEDABAfH493331X46qIlzr1Y/fu3YiNjUV+fj6aNm2K5cuXq9e8QrrEEZ+PK9/52a9fP61LItKVLl26oEmTJup3bJJuccRnIJmZmWjUqJHr8Ycffoju3buz81MDHPFpx+FwYNWqVXj88cdh/X1LsvJ/G+TbOOIzkNJ/2EeOHMGwYcO43x8ZinMub+zYsZjx+04oABh6BsPgM6gmTZrgwQcfZOcnGUJFHZu9evXSuizSCIPPoCIjI9n5SYZQWccm5/KMi3N8dEPn59///nfMnDlT46p8G+f4POOHH37AnXfeyY5NKoPBRwDkC/CaNWswa9YsJCYmolWrVlqX5NMYfJ4zePBgBAUFYfHixWjYsKHW5ZAOMPiojMLCQgQGBgKQ8yKzZs3CxIkT2fmpMgafezgcDrz11luIiYlBx44dAZT9nSYCOMdH5ZR+gVi2bBn++c9/svOTvIJzLu+ZZ57BmDFjUFJSAgAMPboBg48qNXDgQPTr18/V+TlgwADu9k66U1HH5qxZs+Dn56d1aaRTvNRJVRJCYO3atZgyZQqys7Nhs9m444MKeKlTHaV3UgCAYcOGcS6PqsXgoxq5cOECxo0bh+3btwMANm7ciKFDh2pclfdi8CmXn5+Pm2++GZcuXWLHJtUKg49qzDn6e//997F9+3Zu2aIAg08dS5cuRXJyMkd5VCsMPqo1IYTrhfvnn3/GtGnTMHfuXHZ+1gKDr/YcDgeWLFkCq9WKsWPHAij7u0hUUww+UmTEiBHYsGED5/5qicFXO2lpaRgzZgySkpIQEhKCM2fO4KabbtK6LPJS7OokRV5//XV2fpLblO7YTEpKQrNmzfD+++8z9EgRjvhIMXZ+1h5HfNUrPcoDgOHDh2PRokWcyyPFGHykmtKdn2azGceOHUO7du20LkuXGHzV69mzJxITE9GsWTMsX74cAwYM0Lok8hEMPlKVc/R3/vx5LnRdBQZf9Y4dO4b58+djwYIFHOWRqhh85HY7d+7E22+/jWXLlrHz83cMvrKca2wePHgQ69at4yVycisGH7mVEAIdOnTA8ePHOfdXCoPvuvKrryQnJyM6OlrjqsiXsauT3MpkMmHHjh3o27cvOz+pjIrW2Pz4448ZeuR2HPGRRzj3+3v22WfZ+QmO+MqP8h5//HEsXrwYjRo10rgyMgIGH3lU6d3eIyMj8f333yM0NFTrsjzO6MH3wgsv4I033kDTpk2xbNkyPPLII1qXRAbC4COPc3Z+hoeH46GHHgIAFBcXw8/PzzCjPyMGX3FxsWt917y8PMycORN//etfOcojj2PwkS688MILOHXqFJYvX47w8HCty3E7IwWfc43NpUuXYv/+/QgLC9O6JDI4NreQ5rKysvDuu+8iISEB7dq1427vPsS5K/qUKVOQkpKCLVu2aF0SEYOPtGez2fDdd9+V6fwcOHAgMjIytC6N6qiijs1PPvkETzzxhNalEfFSJ+mHkTo/fflSJ3dFJ73jiI90w2QyYcyYMTh+/Lhr9MdLY94nJSWlzChvw4YNDD3SFY74SJeEEFi3bh369OnjanbJyspCWFiYT4z+fG3El5WVBZvN5nq8cuVKDBo0iIFHusTgI69QXFyM6Oho10r93t756SvB5+zYfPnll/HFF1/gnnvu0bokomrxUid5hZMnTyI1NZWdnzpSumPz2rVrSEhI0Lokohph8JFXcC50zc5P7VXWsfnKK69oXRpRjfBSJ3mVijo/3377bTz22GNal1Yr3nqp88cff8SIESPYsUlejSM+8ioVdX5evnxZ67IMIyAgAMeOHWPHJnk1jvjIawkhkJCQgNjYWJjN8j1cWloabr31Vt13fnrTiO/s2bNo2bIl/Pz8AABff/012rdvz8Ajr8URH3ktk8mEAQMGuELv/PnzuPvuu7nfn0qcc3lRUVFYsGCB6/mePXsy9MirMfjIZ5w6dQpmsxnbtm1DVFQUOz8VSEtLQ0xMDKZMmYL8/HykpqZqXRKRahh85DP69OmDEydOoF+/ftztvY5Kd2wmJSWhWbNm+PTTT7Fy5UqtSyNSDef4yOc49/ubMmWKq/Nz/fr1iI2N1bo0Fz3O8WVmZuKRRx5BUlISAGD48OFYtGgRL2uSz+GIj3yOyWTC6NGjXaO/nJwcNG/eXOuydM9ms0EI4RrlrV+/nqFHPokjPvJpQggcPXoUHTt2dD339ddfo0ePHpp2fuplxJeWlgaLxYLIyEgAskGoXr16DDzyaRzxkU8zmUxlQu+jjz5CTEyMx1d9KSgADh8GVqwAZs8GgDcALMTf/gbMnQvs2gX8+qvHyikzl/fkk0+6Arhly5YMPfJ5/loXQORJRUVFCAsLQ0JCAhITE92639+xY8C//gV8+SXw449AcDBQUgLk5QHANADAa68BAQGAxQLY7UBoKHD33cATTwB//CMQGKh6WTfsl9eoUSPY7XZYLBb1T0akQ7zUSYaTnp6OcePGYceOHQCA2NhYLF++HBEREYqPXVgIfPQRMGcOkJIiH5eU1P44oaGA2QxMmAA8/TTQooXi0lw7Kfz1r39Ffn4+mjZtiuXLl2PgwIHKD07kRRh8ZEgVdX7u2LED9957b52PuX07MHKkDLtr19SpMygIMJnkCHDuXMBqrdtxSkpK8OCDD2LPnj0A2LFJxsY5PjKk8p2fDRs2xJ133lmnY2VlAY8+CgweDGRmqhd6gJwbtNuBVauANm2A5OS6HcfPzw/3338/OzaJwBEfEYQQ+OWXX9CsWTMAQE5ODj777DMMGTKk2rm/r74CBg0CcnNlSLmbxQKMHQssWAD8vnRmpdLS0nDhwgXExMQAAAoLC5GTk8PAI8PjiI8Mz2QyuUIPAF588UU8+uij1XZ+fvwx0K8fcOWKZ0IPAPLzgXfekY0vhYUVf0/pjs2hQ4ciMzMTABAYGMjQIwKDj+gGXbt2dXV+Vrbb+7//DQwbJoPI0/LygC++AOLigOLisl8rvSt6fn4+evfurfudKog8jZc6iSpQvvMzLi4Oy5cvR3h4OL78EhgwwHlbgnasVqB/f2DTJkAIdmwS1RSDj6gS5Xd7b9CgAfbuPYEePcKRna11dVJICLBwIbB37whs2LABAHdFJ6oOg4+oGs7Rn81mQ27u+9i5s/L5NS2EhADvvJOMqVMHY+nSpRzlEVWDwUdUA0IIbNxYiCefDNL8Emd5/v7AvfcCu3blw2rl6itE1WHwEdXAtWtAy5bynj09CgkBli0Dhg/XuhIi/WNXJ1ENbNgAFBVpXUXlcnPl4td8G0tUPY74iKohBHDLLcC5c1pXUrWQEHmbg4JV14gMgSM+omokJQGXLys/zuzZwNatwOnT8qb3oiIgOxs4ehR4+22gfXtlx8/PB+bNU14nka/jiI+oGn/6E/DJJ8ovI1b384WFcr3PrVvrfo7gYODiRaBBg7ofg8jXMfiIqtGokRyhKfXzz3L0eOaMPF69ekCfPkDXrte/5+RJICqq7ucIC5M3tD/0kPJ6iXwVg4+oCpcvA82bu+++PZMJ+P57oG1b+Tg/v+5bDwFyU9uZM4GXXlKnPiJfxDk+oiocPix3RFCbyQQ0bCi3M2rZ8vrzx44pO25Rkdwxgogq5691AUR6duCAvFVALa1aVd4d+uuvwOTJys9x5IjyYxD5Mo74iKqQmnrjDgjucPIk8D//A+zfr/xYmZmAw6H8OES+iiM+oiqoOdoDZFPLtGlymbFmzYDYWOC224B27eToMj4e2LhR2Tn8/OT+gO64REvkC9jcQlSF2Fjgs8/cd3w/P2DnTqB3b/k4Nxe49Vbgl1/qfsyAAHnZtH59dWok8jW81ElUheBg9x6/pARISLj+OCQE6NZN2TGLi91fN5E3Y/ARVUGtLe169Kj4pnKTCejbt+xzSq/BmM1y1EdEFeMcH1EV7r5b3lendCui+HjgscfkrQbffit3eWjcGOjXT87vOWVnA3v3KjvXzTfLQCWiijH4iKrQubNsRFFDUJBcUaWyVVV++03e1/fbb8rOc999yn6eyNcx+Iiq0KGDXE1FqXfflYF2771yJZhGjeTzV68CKSlyV4UVK4BLl5Sdx2oFundXXi+RL2NXJ1E1brsN+OEHrauomdBQYPduoEsXrSsh0i82txBV4/HHvadLMigIuOsurasg0jcGH1E1Jk70jp3Ng4OBZ56R9wYSUeUYfETVCA+XN5h7Q6fkuHFaV0Ckfww+ohp4/nll2wW5m9kMPPwwcNNNWldCpH9sbiGqASFkt+SBA55ZtLq2LBa5hdIf/qB1JUT6xxEfUQ2YTMAHH8jmEb0JCZEbzzL0iGqGwUdUQy1bAvPmyaDRC5MJaN0amD5d60qIvAcvdRLVghBy3c2DB4HCQq2rkfOOhw5xtEdUGxzxEdWCySR3U2jRQr2lzOrKYgE+/JChR1RbDD6iWmrQAEhOBiIjtdsFwWKRy6D176/N+Ym8GS91EtXRr78CMTHAmTOA3e6Zc5pMMvQ2bgTi4jxzTiJfwxEfUR01bixvbxg9WoaRu1mtct3QffsYekRKcMRHpIKvv5ZbCmVlqbObQ2kmk1yObOpUYNYsbjJLpBSDj0gleXkymJYtk49zcpQdLzBQrsjStSuweDHQqZPiEokIDD4i1eXnA5s3A3PmAOfOyVsgajoK9PeXlzQdDmDsWGDSJHmfHhGph8FH5EZHj8oO0KQkYP9+4Px5eanSbJaXMB0OoKhI3hTfqZNslunaFXjgAe/ZConI2zD4iDyooAC4fFmOAEtKZLjVrw80bKh1ZUTGweAjIiJD4e0MRERkKAw+IiIyFAYfEREZCoOPiIgMhcFHRESGwuAjIiJDYfAREZGhMPiIiMhQGHxERGQoDD4iIjIUBh8RERkKg4+IiAyFwUdERIbC4CMiIkNh8BERkaEw+IiIyFAYfEREZCgMPiIiMhQGHxERGQqDj4iIDIXBR0REhsLgIyIiQ2HwERGRoTD4iIjIUBh8RERkKAw+IiIyFAYfEREZCoOPiIgMhcFHRESGwuAjIiJDYfAREZGhMPiIiMhQGHxERGQo/w9aFCJRiVNAFQAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 找到测量结果中出现几率最大的比特串\n",
    "cut_bitstring = max(prob_measure, key=prob_measure.get)\n",
    "print(\"找到的割的比特串形式：\", cut_bitstring)\n",
    "\n",
    "# 在图上画出上面得到的比特串对应的割\n",
    "node_cut = [\"blue\" if cut_bitstring[v] == \"1\" else \"red\" for v in V]\n",
    "\n",
    "edge_cut = []\n",
    "for u in range(n):\n",
    "    for v in range(u+1,n):\n",
    "        if (u, v) in E or (v, u) in E:\n",
    "            if cut_bitstring[u] == cut_bitstring[v]:\n",
    "                edge_cut.append(\"solid\")\n",
    "            else:\n",
    "                edge_cut.append(\"dashed\")\n",
    "\n",
    "nx.draw(\n",
    "        G,\n",
    "        pos,\n",
    "        node_color=node_cut,\n",
    "        style=edge_cut,\n",
    "        **options\n",
    ")\n",
    "ax = plt.gca()\n",
    "ax.margins(0.20)\n",
    "plt.axis(\"off\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到，在这个例子中 QAOA 找到了图上的一个最大割。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_______\n",
    "\n",
    "## 参考文献\n",
    "\n",
    "[1] Farhi, E., Goldstone, J. & Gutmann, S. A Quantum Approximate Optimization Algorithm. [arXiv:1411.4028 (2014).](https://arxiv.org/abs/1411.4028)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "3b61f83e8397e1c9fcea57a3d9915794102e67724879b24295f8014f41a14d85"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.13"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
